\chapter{Лекция 3}

\section{Задание конкретного синтаксиса языка}

Пусть $X$ - некоторый алфавит, язык есть подмножество $L \subseteq X^{*}$. Нас интересуют следующие задачи:

\begin{itemize}
\item Конструктивное задание языка

\item Распознование предложений (слов) языка

\item Преобразование цепочек языка
\end{itemize}

Вначале мы будем рассматривать первые две задачи, преобразование оставим на потом.

\subsection{Два подхода к заданию языка}

Первый способ задания языка называется генеративный, т. е. создание такой системы, которая позволяет построить все цепочки данного языка и только их.
Альтернативным способом является аналитический способ, т. е. задание функции, которая позволяет по заданной цепочке определить принадлежит она языку или нет (хотя
не всегда получается показать, что строка не принадлижит языку, хотя в практических приложениях, такое не встречается).

Исторически первым подходом является генеративный и с него мы и начнем.

\subsection{Формальные грамматики Хомского}

Введем некоторые обозначения:

\begin{itemize}
\item $T$ --- алфавит терминальных символов

\item $N$ --- алфавит нетерминальных символов, причем $N \cap T = \emptyset$

\item $S \in N$ - стартовый нетерминал

\item $R = \{p_i = \alpha_i \rightarrow \beta_i\}$ --- множество правил вывода, причем $\alpha_i,\beta_i \in \left(T\cup N\right)^{*}$, причем $\alpha_i$ содержит как минимум один
нетерминал.
\end{itemize}

\begin{Def}
Четверка $G = \left<T,N,S,R\right>$ - порождающая грамматика Хомского
\end{Def}

Введем бинарное отношение на множестве цепочек из терминалов и нетерминалов $\Rightarrow_G \subseteq {\left(N \cup T\right)^{*}}^2$. Пусть $G$ - порождающая
грамматика Хомского, тогда $\gamma \alpha_i \delta \Rightarrow_G \gamma \beta_i \delta$ для $\forall p_i = \alpha_i \rightarrow \beta_i \in R$ и
$\forall \gamma,\delta \in \left(N\cup T\right)^{*}$

Рефлексивно-транзитивное замыкание отношения $\Rightarrow_G$ обозначается как $\Rightarrow_G^{*}$.

\begin{Def}
Пусть $G$ - порождающая грамматика Хомского, тогда $L\left(G\right) = \{w \in T^{*} | S \Rightarrow_G^{*} w\}$ - язык порождаемый грамматикой $G$.
\end{Def}

Все такие грамматики называются грамматиками типа 0, а соответствующие им языки языками типа 0. Однако, накладывая ограничения на правила вывода, можно в грамматиках
типа 0 выделить некоторые подклассы, которые будут важны для нас.

\paragraph{Примеры:}

Рассмотрим алфавит терминалов $T = \{a,b,c\}$. Нужно построить грамматику генерирующую все непустые цепочки над алфавитом терминалов, для этого определим алфавит
нетерминалов $N = \{S, S'\}$, и набор правил вывода $R = \{S \rightarrow SS, S \rightarrow a, S \rightarrow b, S \rightarrow c\}$

Теперь построим грамматику генерирующую только слова четной длинны, например, так
$R = \{S \rightarrow SS, S \rightarrow KK, K \rightarrow a, K\rightarrow b, K\rightarrow c, S \rightarrow \varepsilon\}$

Теперь сгенерируем грамматику генерирующую правильные скобочные последовтаельности: $R = \{S \rightarrow (S)S, S \rightarrow \varepsilon\}$

Теперь построим палиндром из $T = \{a,b,c\}$, для этого используем правила $R = \{S \rightarrow \varepsilon, S \rightarrow aSa, S\rightarrow bSb, S\rightarrow cSc, S \rightarrow a, S\rightarrow b, S\rightarrow c\}$

Теперь построим грамматику генерирующую выражения из терминалов $T = \{x,+,-,*,(,)\}$, для этого используем правила:
$R = \{S \rightarrow S + T, S \rightarrow T, T \rightarrow T * P, T \rightarrow P, P \rightarrow x, P \rightarrow (S)\}$

Теперь построим грамматику с терминалами $T = \{a,b\}$, требуется сгенерировать язык $L = \{a^nb^n | n \ge 0\}$, для этого воспользуемся правилами $R = \{S \rightarrow \varepsilon, S \rightarrow aSb\}$

Теперь еще один $T = \{a,b,c\}$, требуется сгенерировать язык вида $L = \{a^nb^nc^n | n > 0\}$. Тут все уже сложнее, воспользуемся правилами $R = \{S \rightarrow aBN, B \rightarrow aBN, B \rightarrow H, HN \rightarrow bHM, MN \rightarrow NM, cN \rightarrow Nc, M \rightarrow c, H \rightarrow \varepsilon\}$, есть и другой вариант проще:
$R = \{S \rightarrow abc, S \rightarrow aBSc, Ba \rightarrow aB, Bb \rightarrow bb\}$

Теперь пусть есть алфавит нетерминалов $T = \{a,b\}$, требуется построить грамматику генерирующую все слова, в которых кол-во $a$ и $b$ совпадает. Для этого воспользуемся правилами $R = \{S \rightarrow aSbS, S \rightarrow bSaS, S \rightarrow \varepsilon\}$

\paragraph{Домашнее задание}
Построить грамматики пораждающие следющие языки:
\begin{itemize}
\item $T = \{a,b\}$, $L = \{a^nb^m | n\not= m\}$

\item $T = \{a,b,c\}$, $L = \{w | \#a = \#b = \#c\}$

\item $T = \{a,b\}$, $L = \{w | \#b = 2\times \#a\}$

\item $T = \{0,1\}$, $L = \{w | \text{ нет двух единиц подряд}\}$

\item $T = \{0,1,*\}$, <непустая двоичная строка s> <непустая последовательность *> <непустая двоичная строка s>
\end{itemize}

\subsection{Иерархия Хомского}

Мы уже познакомились с самым общим классом грамматик - классом 0. Если задать ограничения на вид правил, то можно выделить некоторые другие классы грамматик, являющиеся
подклассами класса 0. Список классов грамматик:

\begin{itemize}
\item Класс 0, в правой части правил хотябы один нетерминал (см. выше)

\item Класс 1, правила вида $\alpha A \beta \rightarrow \alpha \gamma \beta$, где $A \in N$, $\gamma \in \left(N \cup T\right)^{*}$ и $\gamma \not= \varepsilon$.
Эти грамматики называются контекстно-зависимыми или нескоращающие, так как длинна правой части правила не меньше длинны левой части правила. Несокращаемость
этой грамматики гарантирует надежную проверку принадлежности конечной цепочки языку.

\item Класс 2, правила вида $A \rightarrow \beta$, где $A \in N$ и $\beta$ - непустая цепочка над $N\cup T$. Такие грамматики называются контекстно свободными, т. е.
любой нетерминал заменяется независимо от контекста.

\item Класс 3, правила вида $A \rightarrow b$ или $A \rightarrow bB$, где $A,B \in N$, а $b \in T$, такие грамматики называются автоматными или регулярными.
\end{itemize}

Грамматики образуют правильную вложенность, такая иерархия называется иерархией Хомского. Теперь возвращаясь к языкам, говорят, что язык $L$ принадлежит классу $i$,
если существует грамматика класса $i$ пораждающая $L$. При этом языки могут порождаться различными грамматиками, в том числе для автоматного языка может существовать
контекстно-свободная грамматика.

\subsection{Стартовый нетерминал и пустая цепочка}

По определению, принадлежность пустой строки сразу относит язык к классу 0, что не всегда неудобно, сущестует подход, который позволяет задать требования на стартовый
нетерминал, так чтобы пустая строка выводилась только напрямую из стартового нетерминала.

Рассмотрим грамматики такие, что стартовый нетерминал не входит не в одну правую часть ни одного правила, понятно, что мы не сужаем множество грамматик, так как
удовлетворить это требование можно элементарным преобобразованием. Добавим к нашим классам грамматик (кроме класса 0, там пустая цепочка никак не мешает)
возможность использовать правило $S \rightarrow \varepsilon$, в таких грамматиках пустая строка выводима единственным способом, но при этом все остальные свойства
языков и грамматик никак не поменяются.

\subsection{Регулярные языки}

Сразу построим распознаватель цепочки регулярного языка, для этого рассмотрим некоторую грамматику языка $G = \left<T,N,S,R\right>$, где $R = \{A\rightarrow b, A \rightarrow aB, S \rightarrow \varepsilon, ...\}$
(см. выше класс 3). Построим граф в котором кажому правилу вида $A \rightarrow a_i | \varepsilon$ сопоставим ребро в некоторую единую вершину $F$, а каждому правилу $A \rightarrow b_iC_i$
сопоставим ребро с меткой $b_i$ ведущей в врешину $C_i$. Итого имеем для каждого нетерминала в грамматике существует вершина в графе, кроме того в граф добавляется вершина $F$, и в
графе существует ребро между вершинами $C_i$ и $C_j$, помеченное меткой $c$, если существует правило вида $C_i \rightarrow cC_j$, и есть ребро между $C_i$ и $F$, помеченое
меткой $c$, если существует правило $C_i \rightarrow c$

Рассмотрим грамматику с правилами $R = \{S \rightarrow aA, A \rightarrow aA, A \rightarrow b, S \rightarrow b\}$

TODO: вставить картинку (Вершины S,A,F и ребра (S,A,a), (A,A,a), (A,F,b), (S,F,b)) (посмотреть graphviz)

Построенный граф - граф переходов недетерминированного конечного автомата, его можно использовать для распознавания автоматов. Недетерминированность проявляется
в том, что из некоторой вершины может выходить два ребра с одной пометкой. Но такой автомат всегда можно преобразовать в детерминированный.